class Solution(object):
    def monotoneIncreasingDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        s = [int(num) for num in list(str(n))]
        st = [s[0]]
        index = 1
        while index < len(s):
            if s[index] >= st[-1]:
                st.append(s[index])
                index += 1
            else:
                break
        if index < len(s):
            flag = False
            for k in range(len(st) - 1, 0, -1):
                if st[k] == st[k - 1]:
                    st[k] = 9
                else:
                    st[k] -= 1
                    flag = True
                    break
            if not flag:
                if st[0] > 1:
                    st[0] -= 1
                else:
                    del st[0]
        while index < len(s):
            st.append(9)
            index += 1
        return sum([num * 10 ** (len(st) - 1 - i) for i, num in enumerate(st)])


data = Solution()
n = 4321
print(data.monotoneIncreasingDigits(n))
